# -*- coding: utf-8 -*-
'''
@author: Ricardo Faria 6315 e Luís Freitas 5602
@date: 8 abril de 2013
Classe que permite criar um obtecto Heapsort
'''
import math
import sys

'''
classe heapsort
'''
class Heapsort:
    
    def __init__(self, A):
        '''
        Contrutor da classe
        @param A: Lista a receber
        '''
        self.A = A

    
    def max_heapify(self, i):
        ''' 
        Este metodo tem como funçao tornar a raiz da arvore maior que os
        seus filhos, a chamada propriedade max-heap
        @param i: Indice
        '''
        global heapsize
        l = 2*i     #indice da raiz da esquerda
        r = 2*i+1   #indice da raiz da direita
        
        #se o indice da raiz da esquerda for menor ou igual
        #ao ao heapsize-1 o maior passa a ser o indice de l
        if l <= heapsize-1 and self.A[l] > self.A[i]:
            largest = l
         #caso contrario o maior passa a ser o indice i           
        else:
            largest = i
        #se o indice da direita for menor que o heapsize
        #e o elemento na posiçao r for maior que o elemento na posiçao lasgest
        #entao o largest passa a estar no indice r
        if r <= heapsize and self.A[r] > self.A[largest]:
            largest = r
        #se o indice lasgest for diferente de i entao
        #e efetuada a troca do elemento na posiçao i com o da posiçao largest
        if largest != i:
            self.A[i], self.A[largest] = self.A[largest], self.A[i]
            self.max_heapify(largest)
   
    
    def build_max_heap(self):
        '''
        metodo que constroi uma heap a partir da lista que recebe do construtor
        '''
        for i in reversed(range(0, (int(math.floor(len(self.A)/2))))):
            self.max_heapify(i)

    
    def heapsort(self):
        '''
        Metodo heapsort que tem como funçao ordenadar os elementos colocando os elementos de topo
        da heap apropriadamente
        '''
        global heapsize
        last = len(self.A)-1 #indice do ultimo elemento
        heapsize = len(self.A)-1 
        self.build_max_heap()
        #ciclo decrescente
        for i in reversed(range(0, len(self.A))):
            #troca entre os elementos na posicao i e 0
            #para que fiquem ordenados
            self.A[0], self.A[i] = self.A[i], self.A[0]
            heapsize = heapsize - 1
            self.max_heapify(0)
        #coloca os ultimos dois elementos na ordem correcta
        if self.A[last] < self.A[last-1]:
            self.A[last] , self.A[last-1] = self.A[last-1], self.A[last]
        

